import java.util.*;


public class Solution_test {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        // write code here
        // 使用快速排序的优化算法，分三部分
        int len = a.length;
        int l = 0 , r = len-1 ;//左边界，右边界

        int ret = quickSort(a,l,r,K);//传入参数，数组，左右边界，第K大
        String str = a.toString();
        return ret;
        // int ret = a[K-1];
        // return ret;
    }
    public int quickSort(int[] nums , int l , int r , int k){
        if(l == r){
            return nums[l];
        }
        //生成一个随机数
        int index = new Random().nextInt(r-l+1) + l;
        int key = nums[index];
        int left = l - 1 , right = r + 1 , i = 0;
        while(i < right){
            if(nums[i] > key){
                swap(nums,i,--right);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,i++,++left);
            }
        }
        // 三部分区间 [l,left] [left+1,right-1] ,[right,r]
        int a = left - l + 1 ;
        int b = right - left -1;
        int c = r - right + 1;
        if(k <= a){
            return quickSort(nums,l,left,k);
        }else if( a + b >= k){
            return key;
        }else{
            return quickSort(nums,right,r,k);
        }
    }
    public void swap(int[] nums , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }

    public static void main(String[] args) {
        Solution_test Solution_test = new Solution_test();
        int[] nums = {1,3,5,2,2,5,7,7,7,8,8};
        Solution_test.findKth(nums,5,7);
    }
}
